package leetbook.stack;

import java.util.Arrays;

public class Solution378 {


    public static void main(String[] args) {

        int[][] matrix = {{1,1,3,8,13},{4,4,4,8,18},{9,14,18,19,20},{14,19,23,25,25},{18,21,26,28,29}};
        int k = 13;
        System.out.println(new Solution378().kthSmallest(matrix,k));
    }


    /**
     * 思路一：元素下标从1开始，那么从元素[1,1]到[i,i]确定一块方形的区域R[i]，它比剩余的数都小
     * 只要我们定位到R[i]刚好包含第k个元素，再对其中元素排序查找即可
     * 有问题，R[i]不一定比剩余的数都小
     */
    public int kthSmallest1(int[][] matrix, int k) {
        int n = matrix.length;
        int i = (int)Math.sqrt(k);
        if(i*i==k) return matrix[i-1][i-1]; //刚好在右下角
        //如果i*i<k，即R[i]中没有第k个元素，那么R[i+1]中一定包含第k个元素，对应matrix的下标是[i,i]确定的方形
        //而且第k个元素一定在matrix[0:i,0:i]-matrix[0:i-1,0:i-1]的部分里
        int left = k-i*i;
        //从matrix[0:i,0:i]-matrix[0:i-1,0:i-1]的部分里找到第left个元素即可
        int[] temp = new int[2*i+1];
        System.arraycopy(matrix[i],0,temp,0,i+1); //复制行
        for (int j = i+1, l = 0; j < temp.length; j++,l++) { //复制列
            temp[j] = matrix[l][i];
        }
        Arrays.sort(temp);
        return temp[left-1];
    }

    /**
     * 暴力，复杂度n*n*2*logn
     */
    public int kthSmallest2(int[][] matrix, int k) {
        int n = matrix.length;
        int[] temp = new int[n*n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(matrix[i],0,temp,i*n,n);
        }
        Arrays.sort(temp);
        return temp[k-1];
    }

    /**
     * 二分
     * @param matrix
     * @param k
     * @return
     */
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int small = matrix[0][0], big = matrix[n-1][n-1], mid = 0;
        while (small<=big){
            mid = (small+big)>>1;
            int notBiggerMid = notBiggerNum(matrix,mid);
            if(notBiggerMid<k){ //要找的值一定大于mid
                small = mid+1;
            }else if(notBiggerMid>k){ //要找的值不大于mid
                // 当要找的值有多个时，可能出现这种情况
                if(notBiggerNum(matrix,mid-1)<k) break;
                big = mid-1;
            }else { //此时mid可能不在matrix里，但可以确定的是要找的值不大于mid，否则它至少是第k+1个数
                //如果不大于mid的数字有k个，不大于mid-1的数字小于k个，那么mid就是要找的值
                if(notBiggerNum(matrix,mid-1)<k) break;
                //否则，要找的值肯定不大于mid-1
                big = mid-1;
            }
        }
        return mid;
    }

    /**
     * 用于统计matrix中有多少数字不大于k
     * @param matrix
     * @param m
     * @return
     */
    public int notBiggerNum(int[][] matrix, int m){
        int count = 0;
        //从左下开始找
        int n = matrix.length;
        int i = n-1, j = 0;
        while (j<n){ //每轮循环只计算本列
            while (i>=0&&matrix[i][j]>m) i--; //找到当前列第一个不大于m的数字
            count += i+1;
            if(i<0) break; //由于大于和小于等于k的两部分数字分界线是近似对角的，如果当前列就已经到顶了，后面的列也不存在小于等于m
            j++;
        }
        return count;
    }


}
